package interview.algorithms.offer;

import common.ListNode;
import common.TreeNode;
import common.Util;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 剑指offer
 * @author fance
 * @date 2018/5/28 9:20
 */
public class Solution {


    // dfs时使用
    private int[][] next = {{0,-1},{0,1},{-1,0},{1,0}};

    // 按照目录做题，故不写注释   3.
    public boolean duplicate(int[] nums,int len,int[] dup) {
        for (int i = 0; i < len; i++) {
            while (nums[i] != i && nums[i] != nums[nums[i]]) {
                Util.swap(nums, i, nums[i]);
            }

            if (nums[i] != i && nums[i] == nums[nums[i]]) {
                dup[0] = nums[i];
                return true;
            }
        }
        return false;
    }


    public boolean find(int[][] m,int target) {
        if (m == null || m.length < 1) {
            return false;
        }

        int row = 0;
        int col = m[0].length - 1;
        while (row < m.length && col >= 0) {
            if (target == m[row][col]) {
                return true;
            } else if (target < m[row][col]) {
                col--;
            } else {
                row++;
            }
         }
         return false;
    }


    public String replaceSpace(String s) {
        int n = s.length();
        int spaceCnt = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == ' ') {

                spaceCnt++;
            }
        }
        if (spaceCnt == 0) {
            return s;
        }
        char[] temp = new char[n + 2 * spaceCnt];
        int j = temp.length - 1;
        int i = n - 1;
        while (i >= 0) {
            if (s.charAt(i) == ' ') {
                temp[j--] = '0';
                temp[j--] = '2';
                temp[j--] = '%';
                i--;
            } else {
                temp[j--] = s.charAt(i--);
            }
        }
        return new String(temp);

        // replaceAll()
    }


    public List<Integer> printListRevI(ListNode head) {
        List<Integer> res = new ArrayList<>();
        while (head != null) {
            res.add(head.val);
            head = head.next;
        }
        Collections.reverse(res);
        return res;
    }
    public List<Integer> printListRevII(ListNode head) {
        List<Integer> res = new ArrayList<>();
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        while (pre != null) {
            res.add(pre.val);
            pre = pre.next;
        }
        return res;
    }


    public TreeNode reConstructTree(int[] pre,int[] in) {
        return reConstructTreeCore(pre,0,pre.length - 1,in,0,in.length - 1);
    }
    private TreeNode reConstructTreeCore(int[] pre,int preL,int preR,int[] in,int inL,int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preL]);
        if (preL != preR) {
            int idx = inL;
            while (idx <= inR && in[idx] != root.val) {
                idx++;
            }
            int leftTreeLen = idx - inL;
            root.left = reConstructTreeCore(pre,preL + 1,preL + leftTreeLen,in,inL,idx - 1);
            root.right = reConstructTreeCore(pre,preL + leftTreeLen + 1,preR,in,idx + 1,inR);

        }
        return root;
    }




    /*public TreeNode getNext(TreeNode node) {
        if (node == null) return null;
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        } else {
            TreeNode parent = node.next;
            while (parent != null) {
                if (parent.left == node) return parent;
                parent = parent.next;
                node = node.next;
            }
        }
        return null;
    }*/

    LinkedList<Integer> stack1 = new LinkedList<>();
    LinkedList<Integer> stack2 = new LinkedList<>();
    public void push(int val) {
        stack1.push(val);
    }
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }



    private int[] fib = new int[40];
    {
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }
    public int fibonacci(int n) {
        return fib[n];
    }

    public int jumpFloor(int target) {
        if (target < 3) {
            return target;
        }
        int[] dp = new int[target];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target - 1];
    }
    public int jumpFloorII(int target) {
        if (target == 1) {
            return 1;
        }
        return jumpFloorII(target - 1) * 2;
    }

    // 矩阵覆盖 同fib

    public int findMinInRotateArr(int[] arr) {
        int lo = 0;
        int hi = arr.length - 1;
        if (arr[hi] > arr[lo]) {
            return -1;
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == arr[lo] && arr[lo] == arr[hi]) {
                return seachMin(arr,lo,hi);
            }
            if (hi - lo == 1) {
                break;
            }

            if (arr[mid] >= arr[lo]) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return arr[hi];
    }
    private int seachMin(int[] arr,int lo,int hi) {
        int res = arr[lo];
        for (int i = lo + 1; i <= hi; i++) {
            res = Math.min(res,arr[i]);
        }
        return res;
    }





    public boolean hasPath(char[][] m, int rows,int cols,char[] s) {
        if (rows == 0 || cols == 0) {
            return false;
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPathCore(m,rows,cols,s,new boolean[rows][cols],0,i,j)) {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean hasPathCore(char[][] m, int rows,int cols,char[] s,boolean[][] used,int path,int r,int c) {
        if (path == s.length) {
            return true;
        }
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return false;
        }
        if (m[r][c] != s[path]) {
            return false;
        }
        if (used[r][c]) {
            return false;
        }
        used[r][c] = true;
        for (int i = 0; i < next.length; i++) {
            if (hasPathCore(m,rows,cols,s,used,path + 1,r + next[i][0],c + next[i][1])) {
                return true;
            }
        }
        used[r][c] = false;
        return false;
    }




    private int cnt = 0;
    public int moveCnt(int threshold, int rows,int cols) {
        int[][] digitSum = new int[rows][cols];
        initDigitSum(digitSum,rows,cols);
        dfsForMoveCnt(digitSum,new boolean[rows][cols],threshold,rows,cols,0,0);
        return cnt;
    }
    private void dfsForMoveCnt(int[][] digitSum,boolean[][] visited,int threshold,int rows,int cols,int r,int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return;
        }
        if (visited[r][c]) {
            return;
        }
        visited[r][c] = true;
        if (digitSum[r][c] > threshold) {
            return;
        }
        cnt++;
        for (int i = 0; i < next.length; i++) {
            dfsForMoveCnt(digitSum,visited,threshold,rows,cols,r + next[i][0], c + next[i][1]);
        }
    }
    private void initDigitSum(int[][] digitSum,int rows,int cols){
        int[] digitSumOne = new int[Math.max(rows,cols)];
        for (int i = 0; i < digitSumOne.length; i++) {
            int n = i;
            while (n > 0) {
                digitSumOne[i] += n % 10;
                n /= 10;
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                digitSum[i][j] = digitSumOne[i] + digitSumOne[j];
            }
        }
    }






    // 二进制1的个数
    /*Integer.bitCount();
    n & (n - 1)*/





    public double power(double base,int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        boolean isNeg = false;
        if (exponent < 0) {
            exponent = -exponent;
            isNeg = true;
        }
        double pow = power(base * base,exponent / 2);
        if (exponent % 2 != 0) {
            pow *= base;
        }
        return isNeg ? 1 / pow : pow;
    }






    public  boolean matchRev(String input,String pattern){
        if(input==null||pattern==null) {
            return false;
        }
        return matchCore(input,0,pattern,0);
    }
    private  boolean matchCore(String input,int i,String pattern,int p){
        if (input.length() == i && p == pattern.length()) {
            return true;
        }
        if((i!=input.length())&&(pattern.length()==p)){
            return false;
        }
        if((input.length()==i)&&(pattern.length()!=p)){
            //出口3，字符串input到末尾，pattern还没有到末尾
            return false;
        }

        if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '*') {
            if((input.charAt(i)==pattern.charAt(p))||(pattern.charAt(p)=='.')){
                //首字母相匹配
                return matchCore(input,i+1,pattern,p+2) //*表示出现1次
                ||matchCore(input,i+1,pattern,p)    //*表示出现多次
                 ||matchCore(input,i,pattern,p+2);   //*表示出现0次 ， a ...  p* ...
            } else {
                //首字母不匹配
                return matchCore(input,i,pattern,p+2);
            }
        }

        if((input.charAt(i)==pattern.charAt(p))||(pattern.charAt(p)=='.')){
            //pattern第二个字母不是*，且首字母匹配
            return matchCore(input,i+1,pattern,p+1);
        }
        return false;  //其余情况全部不匹配

    }

    public boolean match(char[] s,char[] pattern) {
        int n = s.length,m = pattern.length;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            if (pattern[i - 1] == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i - 1] == pattern[j - 1] || pattern[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pattern[j - 1] == '*') {
                    if (pattern[j - 2] != s[i - 1] && pattern[j - 2] != '.') {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }



    public boolean isNumeric(String s) {
        s = s.substring(2);
        try {
            Integer.valueOf(s);
        } catch (Exception e) {
            return false;
        }
        return true;
    }


    /**
     * 21 奇元素在偶元素之前
     * @param a
     */
    public void reOderArray(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        int oddCnt = 0;
        for (int num: a
             ) {
            if (num % 2 == 1) {
                oddCnt++;
            }
        }
        int[] copy = a.clone();
        int i = 0, j = oddCnt;
        for (int num : copy) {
            if (num % 2 == 1) {
                a[i++] = num;
            } else {
                a[j++] = num;
            }
        }
    }


    /**
     * 倒数第k个节点
     * @param head
     * @param k
     * @return
     */
    public ListNode findKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode fast = head,slow = head;
        while (fast != null && k-- > 0) {
            fast = fast.next;
        }
        if (k > 0) {
            return null;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    public ListNode entryNodeOfLoop(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head,slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                fast = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }


    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }



    public ListNode merge(ListNode l1,ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return head.next;
    }


    public boolean hasSubTree(TreeNode root1,TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return isSubTree(root1,root2) || hasSubTree(root1.left,root2) || hasSubTree(root1.right,root2);
    }
    private boolean isSubTree(TreeNode root1,TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (root2 == null) {
            return true;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return isSubTree(root1.left,root2.left) && isSubTree(root1.right,root2.right);
    }


    public void mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        mirror(root.left);
        mirror(root.right);
    }




    @Test
    public void test() {


        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        for (Integer i : printListRevII(listNode1)) {
            System.out.println(i);
        }
        /*
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        listNode4.next = listNode5;
        listNode5.next = listNode6;
       *//* while (listNode1 != null) {
            System.out.print(listNode1.val + " ");
            listNode1 = listNode1.next;
        }
        System.out.println();*//*
       // ListNode res = reverseList(listNode1);
        ListNode res = merge(listNode1,listNode4);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }*/
    }
}
